Multimedia capabilities can be incorporated into a wide range of devices, including digital televisions, digital direct broadcast systems, wireless communication devices, personal digital assistants (PDAs), laptop computers, desktop computers, digital cameras, digital recording devices, cellular or satellite radio telephones, and the like. Digital multimedia coding can provide significant improvements over conventional analog systems in creating, modifying, transmitting, storing, recording and playing full motion multimedia sequences. Broadcast networks, for example, may use multimedia coding to facilitate the broadcast of one or more channels of multimedia sequences to wireless subscriber devices.
A number of different multimedia coding standards have been established for coding digital multimedia sequences. The Moving Picture Experts Group (MPEG), for example, has developed a number of standards including MPEG-1, MPEG-2 and MPEG-4. Other standards include the International Telecommunication Union (ITU) H.263 standard, QuickTime™ technology developed by Apple Computer of Cupertino Calif., Video for Windows™ developed by Microsoft Corporation of Redmond, Wash., Indeo™ developed by Intel Corporation, RealVideo™ from RealNetworks, Inc. of Seattle, Wash., and Cinepak™ developed by SuperMac, Inc. Furthermore, new standards continue to emerge and evolve, including the emerging ITU H.264 standard and a number of proprietary standards. The ITU H.264 standard is also set forth in MPEG-4 Part 10, entitled “Advanced Audio Coding.”
Many multimedia coding standards support data compression, which reduces the overall amount of data that needs to be transmitted for effective transmission of multimedia frames. The MPEG standards and the ITU H.263 and ITU H.264 standards, for example, support coding techniques that utilize similarities between successive video frames, referred to as temporal or inter-frame correlation, to provide inter-frame compression. Such inter-frame compression is typically achieved via motion estimation and motion compensation coding techniques. In addition, some multimedia coding techniques may utilize similarities within frames, referred to as spatial or intra-frame correlation, to compress the video frames.
Most inter-frame compression techniques utilize block-based coding, which divides multimedia frames into blocks of data and correlates the blocks with those of other frames in the multimedia sequence. By encoding the differences between a current block and a predictive block of another frame, data compression can be achieved. The encoder typically divides a multimedia frame to be transmitted into blocks of data, referred to as “macroblocks.” The macroblocks may also be further sub-divided into partitions or sub-partitions. The ITU H.264 standard supports 16 by 16 macroblocks, 16 by 8 partitions, 8 by 16 partitions, 8 by 8 partitions, 8 by 4 sub-partitions, 4 by 8 sub-partitions and 4 by 4 sub-partitions. Other standards may support differently sized blocks, macroblocks, partitions and/or sub-partitions.
For each block (macroblock, partition or sub-partition) in a multimedia frame, the encoder searches similarly sized blocks of one or more immediately preceding video frames (or subsequent frames) to identify a similar block, referred to as the “prediction block” The process of comparing a current video block to video blocks of other frames is generally referred to as motion estimation. Once a “prediction block” is identified for a given block to be coded, the encoder can encode the differences between the current block and the prediction block. This process of encoding the differences between the current block and the prediction block includes a process referred to as motion compensation. Motion compensation comprises creating a difference block indicative of the differences between the current block to be encoded and the prediction block. In particular, motion compensation usually refers to the act of fetching the prediction block using a motion vector, and then subtracting the prediction block from an input block to generate a difference block.
After motion compensation has created the difference block, a series of additional encoding steps are typically performed to further encode the difference block. These additional steps may include discrete cosine transform, scalar quantization, raster-to-zigzag reordering, run-length encoding, Huffman encoding, or the like. An encoded difference block can be transmitted along with a motion vector that indicates which block from the previous frame (or subsequent frame) was used for the encoding. A decoder receives the motion vector and the encoded difference block, and decodes the received information to reconstruct the multimedia sequences.
In order to improve the coding process, mode decisions are often made during the motion estimation process. These mode decisions may be part of a rate control algorithm, and may be used to determine how the macroblocks should be divided or sub-divided to ensure that a desirable rate-distortion balance is achieved. In this disclosure, the phrase “mode selection” refers to the selection of one or more possible coding modes for a macroblock or the like, e.g., whether the macroblock should be coded as one 16 by 16 block or whether two or more partitions or sub-partitions should be defined for the macroblock. Unfortunately, a full search of every possible coding mode for every macroblock of a video sequence can be computationally prohibitive for many devices or multimedia encoding situations.